package 力扣日常刷题.木22一月.第10天0118;

/**
 * @author 帅小伙
 * @date 2022/1/18
 * @description
 * https://leetcode-cn.com/problems/last-stone-weight-ii/
 * 分成两堆  绝对值之差最小
 */
public class Demo19动态规划中等最后一块石头的重量2 {


    public int lastStoneWeightII(int[] stones) {
        int length = stones.length;
        int sum = 0;
        for (int i = 0; i < length; i++) {
            sum += stones[i];
        }

        int[] dp = new int[sum/2+1];

        for (int i = 1; i <= length ; i++) {
            for (int j = sum/2; j >=stones[i-1] ; j--) {
                dp[j] = Math.max(dp[j],dp[j-stones[i-1]]+stones[i-1]);
            }
        }
        return sum - 2*dp[sum/2];
    }
}
